package top.minuy.structure.queue.deque;
/**
 * @author Minuy
 * @time 22:39
 * @date 2021/8/22
 */
public class LoopDeque<E> implements Deque<E> {

    // 数据
    E[] data;
    // 头部索引，尾部索引
    int front, tail;
    // 大小
    int size;

    public LoopDeque(int capacity) {
        this.data = (E[]) new Object[capacity];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopDeque() {
        this(10);
    }

    /**
     * 获取队列大小
     *
     * @return 队列大小
     */
    @Override
    public int getSize() {
        return this.size;
    }

    /**
     * 判断队列是否为空
     *
     * @return 队列是否为空
     */
    @Override
    public boolean isEmpty() {
        return this.size == 0 && this.front == this.tail;
    }

    public int getCapacity() {
        return data.length;
    }

    /**
     * 重新分配大小
     *
     * @param newCapacity 新的容量大小
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];

        // 重新把数组复制到新数组中
        for (int i = 0; i < this.size; i++) {
            newData[i] = this.data[(this.front + i) % this.data.length];
        }

        this.front = 0;
        this.tail = size;

        this.data = newData;
    }

    /**
     * 容量自动扩大
     */
    private void sizeAutoExpand() {
        if (this.size == this.data.length && this.front == this.tail) {
            resize(this.getCapacity() * 2);
        }
    }

    /**
     * 容量自动缩小
     */
    private void sizeAutoNarrow() {
        if (this.getSize() <= data.length / 4 && this.getCapacity() / 2 != 0) {
            resize(this.getCapacity() / 2);
        }
    }

    /**
     * 从队列前面添加元素
     *
     * @param e 要添加的元素
     */
    @Override
    public void addFront(E e) {
        sizeAutoExpand();

        // 下面这边是因为负数取余有问题
        front--;
        while (front < 0) {
            // 保证front是正数，此时front一定大于0且小于data.length，在一个合理范围内
            front += data.length;
        }

        data[front] = e;
        size++;
    }

    /**
     * 从队列后面添加元素
     *
     * @param e 要添加的元素
     */
    @Override
    public void addLast(E e) {
        sizeAutoExpand();

        this.data[tail] = e;
        this.tail = (this.tail + 1) % this.data.length;
        size++;
    }

    /**
     * 从队列前面移除队列元素
     *
     * @return 被移除的队列元素
     */
    @Override
    public E removeFront() {
        if (this.isEmpty()) {
            throw new IllegalArgumentException("RemoveFront Failed. Deque is empty.");
        }

        E res = this.data[this.front];

        // 提前释放内存
        this.data[this.front] = null;

        this.front = (this.front + 1) % this.data.length;
        this.size--;

        sizeAutoNarrow();

        return res;
    }

    /**
     * 从队列后面移除队列元素
     *
     * @return 被移除的队列元素
     */
    @Override
    public E removeLast() {
        if (this.isEmpty()) {
            throw new IllegalArgumentException("RemoveLast Failed. Deque is empty.");
        }

        this.tail--;
        while (this.tail < 0) {
            this.tail += data.length;
        }

        E res = this.data[this.tail];

        // 提前释放内存
        this.data[this.tail] = null;

        size--;

        sizeAutoNarrow();

        return res;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Loop Deque : size = %d , capacity = %d\n", this.getSize(), this.getCapacity()));
        res.append("front [");
        for (int i = 0; i < this.size; i++) {
            // 顺序对应着头索引对i的循环偏移
            res.append(this.data[(this.front + i) % this.data.length].toString());
            if (i != this.size-1) {
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }
}
